|
In computer science, a WAVL tree or weak AVL tree is a self-balancing binary search tree. WAVL trees are named after AVL trees, another type of balanced search tree, and are closely related both to AVL trees and red–black trees, which all fall into a common framework of rank balanced trees. Like other balanced binary search trees, WAVL trees can handle insertion, deletion, and search operations in time per operation.〔.〕〔 WAVL trees are designed to combine some of the best properties of both AVL trees and red–black trees. One advantage of AVL trees over red–black trees is that they are more balanced: they have height at most (for a tree with data items, where is the golden ratio), while red–black trees have larger maximum height, . If a WAVL tree is created using only insertions, without deletions, then it has the same small height bound that an AVL tree has. On the other hand, red–black trees have the advantage over AVL trees that they perform less restructuring of their trees. In AVL trees, each deletion may require a logarithmic number of tree rotation operations, while red–black trees have simpler deletion operations that use only a constant number of tree rotations. WAVL trees, like red–black trees, use only a constant number of tree rotations, and the constant is even better than for red–black trees.〔〔 WAVL trees were introduced by . The same authors also provided a common view of AVL trees, WAVL trees, and red–black trees as all being a type of rank-balanced tree.〔.〕 ==Definition== As with binary search trees more generally, a WAVL tree consists of a collection of nodes, of two types: internal nodes and external nodes. An internal node stores a data item, and is linked to its parent (except for a designated root node that has no parent) and to exactly two children in the tree, the left child and the right child. An external node carries no data, and has a link only to its parent in the tree. These nodes are arranged to form a binary tree, so that for any internal node the parents of the left and right children of are itself. The external nodes form the leaves of the tree.〔, Section 2.3 Trees, pp. 68–83.〕 The data items are arranged in the tree in such a way that an inorder traversal of the tree lists the data items in sorted order.〔, Chapter 3 Binary Search Trees, pp. 89–114.〕 What distinguishes WAVL trees from other types of binary search tree is its use of ''ranks''. These are numbers, stored with each node, that provide an approximation to the distance from the node to its farthest leaf descendant. The ranks are required to obey the following properties:〔〔 *Every external node has rank 〔In this we follow . In the version described by , the external nodes have rank −1. This variation makes very little difference in the operations of WAVL trees, but it causes some minor changes to the formula for converting WAVL trees to red–black trees.〕 *If a non-root node has rank , then the rank of its parent must be either or . *An internal node with two external children must have rank exactly 1. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「WAVL tree」の詳細全文を読む スポンサード リンク
|